package _binary_tree

import common.TreeNode
import org.junit.Assert
import org.junit.Test
import java.util.*
import kotlin.collections.ArrayList

/*
https://programmercarl.com/0102.%E4%BA%8C%E5%8F%89%E6%A0%91%E7%9A%84%E5%B1%82%E5%BA%8F%E9%81%8D%E5%8E%86.html#_515-%E5%9C%A8%E6%AF%8F%E4%B8%AA%E6%A0%91%E8%A1%8C%E4%B8%AD%E6%89%BE%E6%9C%80%E5%A4%A7%E5%80%BC
https://leetcode.cn/problems/find-largest-value-in-each-tree-row/description/
515. 在每个树行中找最大值

给定一棵二叉树的根节点 root ，请找出该二叉树中每一层的最大值。

示例1：
输入: root = [1,3,2,5,3,null,9]
输出: [1,3,9]
示例2：

输入: root = [1,2,3]
输出: [1,3]
 */
class leetcode_515 {
    @Test
    fun test_1() {
        val root = TreeNode(1)
        val n3 = TreeNode(3)
        val n2 = TreeNode(2)
        val n5 = TreeNode(5)
        val n3_2 = TreeNode(3)
        val n9 = TreeNode(9)
        root.left = n3
        root.right = n2
        n2.left = n5
        n2.right = n3_2
        n2.right = n9
        val actual = largestValues(root)
        val expect = arrayListOf(1, 3, 9)
        Assert.assertEquals(expect.toString(), actual.toString())
    }

    @Test
    fun test_2() {
        val root = TreeNode(1)
        val n2 = TreeNode(2)
        val n3 = TreeNode(3)
        root.left  = n2
        root.right = n3

        val actual = largestValues(root)
        val expect = arrayListOf(1,3)
        Assert.assertEquals(expect.toString(), actual.toString())
    }


    private fun largestValues(root: TreeNode?): List<Int> {
        /**
         * 题型：二叉树的层级遍历
         *
         * 思路：
         * 遍历每一层，找出最大值，然后收集起来
         */
        // S - N
        // T - N
        val result: ArrayList<Int> = ArrayList<Int>()
        if (null == root) {
            return result
        }

        val queue: LinkedList<TreeNode> = LinkedList<TreeNode>()
        queue.offer(root)

        while (!queue.isEmpty()) {
            var max: Int? = null;
            var size: Int = queue.size

            while (size-- > 0) {
                val node: TreeNode = queue.poll()
                if (null == max) {
                    max = node.`val`
                } else if (node.`val` > max) {
                    max = node.`val`
                }

                node.left?.let { queue.offer(it) }
                node.right?.let { queue.offer(it) }
            }
            max?.let { result.add(it) }
        }

        return result
    }
}